////#include <iostream>
////#include<unordered_map>
////#include<algorithm>
////#include<string>
////using namespace std;
////
////int main() {
////    string str1;
////    string str2;
////    while (cin >> str1 >> str2) {
////        sort(str1.begin(), str1.end());
////        sort(str2.begin(), str2.end());
////        int ptr1 = 0;
////        int ptr2 = 0;
////        while (ptr1 < str1.size()) {
////            while (ptr2 < str2.size() && str1[ptr1] == str2[ptr2]) {
////                ptr1++;
////                ptr2++;
////            }
////            ptr1++;
////        }
////        if (ptr2 == str2.size()) {
////            cout << "Yes"<<endl;
////           
////            return 0;
////        }
////        else {
////            cout << "No" << endl;
////          
////        }
////
////    }
////}
//#include <iostream>
//#include<vector>
//#include<cmath>
//using namespace std;
//bool istr(int x)
//{
//	for (int i = 2; i <= sqrt(x); i++)
//	{
//		if (x % i == 0)return false;
//
//
//
//	}
//
//	return true;
//
//
//
//}
//
//
//
//bool count(int x)
//{
//	vector<int>st;
//	while (x)
//	{
//		st.push_back(x % 10);
//		x /= 10;
//	}
//
//	for (int i = 0; i < st.size(); i++)
//	{
//		for (int j = 0; j < st.size(); j++)
//		{
//			if (st[i] != 0 && i != j)
//			{
//				if (istr(st[i] * 10 + st[j]))
//				{
//					return true;
//				}
//
//
//			}
//
//
//
//		}
//	}
//
//	return false;
//
//
//}
//int main() {
//	int ret = 0;
//	int m, n;
//	cin >> m >> n;
//    
//
//
//
//
//}
#include <iostream>
#include<queue>
#include<vector>
using namespace std;
//long long N = 1e9 + 10;
//
//template <class T>
//struct fun
//{
//
//    bool operator()(T st1,T st2)
//    {
//        if (st1.first == st2.first)return st1.second < st2.second;
//        else return st1.first > st2.first;
//    }
//
//};
//int main() {
//    int n, k;
//    vector<int>a(N);
//    vector<int>b(N);
//    cin >> n >> k;
//    priority_queue<pair<int, int>, vector<pair<int, int>>, fun<pair<int, int>>>st;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//    }
//    for (int i = 0; i < n; i++)
//    {
//        cin >> b[i];
//    }
//    for (int i = 0; i < n; i++)
//    {
//        st.push({ a[i],b[i] });
//    }
//    int ret1 = 0;
//    int ret2 = 0;
//    while (k--)
//    {
//
//        auto [x, y] = st.top();
//        st.pop();
//        ret1 += x;
//        ret2 += y;
//    }
//    cout << ret1 << ret2 << endl;
//
//
//
//}
int knapsack(int V, int n, vector<vector<int> >& vw) {

    vector<vector<int>>dp(n, vector<int>(V + 1, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = V; j >= vw[i][0]; j--)


            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i][0]] + vw[i][1]);



    }
    return dp[n - 1][V];
    class Solution {
    public:
        bool isPowerOfThree(int n) {

            while (n && n % 3 == 0)
            {
                n /= 3;
            }
            return n == 1;





        }
    };






}class Solution {
public:
    int lengthOfLastWord(string s) {
        reverse(s.begin(), s.end());
        char* str = &s[0];
        while (*str == ' ')
        {
            str++;
        }
        int count = 0;
        while (*str != '\0' && *str != ' ')
        {

            str++;
            count++;

        }

        return count;








    }
};